package top.lcm889.oj.按算法分类.排序;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author Coder-lcm
 * @date 2021/2/5
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 */
public class T215_数组中的第K大的元素 {

    //普通排序：时间复杂度 O(NlogN)，空间复杂度 O(1)
    public static int findKthLargest_1(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    //堆排序：时间复杂度 O(NlogK)，空间复杂度 O(K)
    public static int findKthLargest_2(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();//最小顶堆（首元素最小）
        for (int num : nums) {
            queue.add(num);
            if (queue.size() > k) { //维持一个高度为k的堆，一旦超过3就把顶部的删除即可
                queue.poll();
            }
        }
        return queue.peek();
    }


    public static void main(String[] args) {
//        System.out.println(findKthLargest_1(new int[]{3, 2, 1, 5, 6, 4}, 2));
        System.out.println(findKthLargest_2(new int[]{3, 2, 1, 5, 6, 4}, 2));
    }
}
